This invention relates to arbitration networks for use in digital data processing systems which share access to a functional device. However, to facilitate an understanding of the invention, we have described a system wherein plural processors of a multiprocessing system share a functional device that comprises a multiported memory unit.
A digital processing system comprises three basic elements: namely, a memory element, an input-output element, and a processor element. The memory element stores information at addressable storage locations therein. This information includes data and instructions for processing the data. The processor element transfers information to and from the memory element, interprets the incoming information as either data or instructions, and processes data in accordance with the instructions. The input-output element communicates with the memory element and processor element in order to transfer data to the system and to obtain processed data from the system.
The basic digital data processing system described above may further incorporate several asynchronously and independently operating processors that transfer information over a common bus. Each processor performs its task in response to its own independent clocking system. This elimination of functional interdependance, under certain conditions, makes multiprocessing systems time-wise more efficient than synchronized multiprocessors. Furthermore, a more economical use of processors can be provided in that the complexity of the respective processors may vary according to the nature of operations that each will perform. To further improve time efficiency of multiprocessor arrangements, cache memory systems also may be incorporated in the respective processing systems as disclosed by U.S. Pat. Nos. 3,848,234 issued to MacDonald. Usually, a cache memory will contain copies of data stored at predetermined locations in a usually larger memory, such as a magnetic core memory, that has a slower access time. The use of cache memory provides faster data retrieval to further increase processing speed.
It also has been desirable to provide a multiprocessing arrangement wherein the several data processors thereof share access to the common functional unit in a manner to maintain the high speeds of data processing operations. Particularly, when several devices share a functional unit, processing delays result from idle processing time that occurs while the interconnect logic circuitry performs interconnection of the several devices to shared unit through the common bus. This situation always occurs when the processing devices and functional unit are interconnected through a common data bus.
To further reduce idle processing time, an efficient time sharing network for distributing the use of the common bus among the several devices is required so that no one device may retain access to the shared unit to the exclusion of other devices. Moreover, the arrangement requires a network for resolving conflicts when more than one device simultaneously request use of the common bus. Such networks for accomplishing time sharing and conflict resolution are known as arbiters or arbitration networks.
The arbiter grants access to the shared unit in accordance with certain established priority rules when a conflict situation occurs. These priority rules may be based upon linear selection rules, ring selection rules, or a mixed priority scheme. The linear selection scheme provides conflict resolution in favor of the requesting device that has the highest assigned fixed priority. The ring selection scheme provides, in effect, a round-robin scheduling of priorities so that each device takes its turn being first in line when a conflict arises. This method typically provides for a shift in priority assignment upon each operational cycle of the shared unit. The mixed priority scheme may incorporate both linear and ring selection rules wherein preference is given to particular devices based upon the current and/or prior grant conditions. An arbitration network may also employ a random access rule for granting access, but the assurance of an equal distribution of access time is then sacrificed. In a multiprocessing system where each processor has equal data transfer capability, a priority scheme that gives each processor equal opportunity to use the shared functional unit is generally desirable. To further insure equitable distribution of access time, the arbitration network may keep a service history of each granted access so that it can modify the priority scheme in response to changing conditions and thereby maintain the desired degree of time distribution of access by the various data processing devices.
The arbitration network may be centralized in the shared functional unit, or the network may be decentralized to the extent that each requesting device may contain its own logic circuitry that determines, based upon monitored use activity of the devices, which of the several requesting devices will next acquire access to the shared unit. Whether the arbitration network is centralized or decentralized, the methods of determination of priorities are generally similar.
In operation, when a request for access to the functional unit is made, the arbitration network initiates its decision cycle to determine which requesting device will next be granted access to the functional unit. When the functional unit is busy while performing an operational cycle, all requests made during the busy condition are held until such time as the operational cycle of the functional unit is complete, whereupon decision logic is initiated to determine which device will next have access. Idle bus periods exist between the arbiter and operational cycles as there is typically no overlap between the performance of two cycles. Moreover, even though it is not necessary, the arbitration network is sequenced through its complete cycle when a sole request is present. An immediate grant to a sole requesting device is all that is necessary. Thus, with the use of a typical arbitration network, maximum time efficiency is sacrificed as idle time periods occur on the common data bus during the sequencing of the decision cycle of the arbitration network.
Accordingly, it is one object of this invention to provide an arbitration network that reduces idle time periods on a common data bus that interconnects several data processing devices and a shared functional unit.
It is another object of this invention to provide an arbitration network that, upon receipt of a request from other devices for access to the shared functional unit while the unit is busy with one device, initiates and completes its arbitration cycle prior to the completion of its operational cycle with said one device, and then grants access to one of said other devices having the then highest assigned priority immediately succeeding the current transaction.
It is another object of this invention to provide an arbitration network that, while the system is idle, grants immediate access to a sole requesting device without the necessity of performing its complete arbitration cycle, thereby further reducing idle time periods on said common data bus.
It is yet another object of this invention to employ the herein described arbitration network in a multiported memory unit connected to a multiprocessing system wherein each data processor or controller thereof share the memory unit through a common data bus.
Additional and further objects of the invention will become more readily apparent upon review of the succeeding disclosure taken in connection with the accompanying drawings.